#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-08 10:57 上午
# @Author  : yangdy
# @File    : 2020-08-08.99.恢复二叉搜索树
# @Software: PyCharmCE
from my_methods import *


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        def mid(root):
            if not root:
                return []
            return mid(root.left) + [root] + mid(root.right)

        nodes = mid(root)

        ns = sorted(nodes, key=lambda x: x.val)

        temps = [nodes[i] for i in range(len(nodes)) if nodes[i] != ns[i]]
        if temps:
            temps[0].val, temps[1].val = temps[1].val, temps[0].val


questions = [
    ([1, 3, None, None, 2],),
    ([3, 1, None, None, 2],),
    ([3, 1, 4, None, None, 2],),
]


tree1 = mk_tree(questions[0][0], TreeNode)

display(tree1)

work(questions, func=lambda q: Solution().recoverTree(mk_tree(q[0], TreeNode)))
